package org.example.SolutionNew001;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Array02 {
    public static void main(String[] args) {
        Array02 a = new Array02();
        int[][] intervals=new int[][]{{1,4},{5,6},{8,10},{15,18}};
        int[][] res=a.merge(intervals);
        for(int i=0;i<res.length;i++){
            System.out.println(Arrays.toString(res[i]));
        }

    }

    public int[][] merge0(int[][] intervals) {
        int n = intervals.length;
        if(n==1) return intervals;

        List<int[]> res = new ArrayList<int[]>();
        //排序
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<i;j++){
                if(intervals[j][0]>intervals[j+1][0]){
                    int[] tmp=new int[]{intervals[j][0],intervals[j][1]};
                    intervals[j][0]=intervals[j+1][0];intervals[j][1]=intervals[j+1][1];
                    intervals[j+1][0]=tmp[0]; intervals[j+1][1]=tmp[1];
                }
            }
        }
        for (int[] interval : intervals) {
            if (res.isEmpty()) res.add(interval);
            int curLength=res.size();
            if(interval[0]<=res.get(curLength-1)[1]){
                res.get(curLength-1)[1]=Math.max(res.get(curLength-1)[1],interval[1]);
            }else{
                res.add(interval);
            }
        }
        return res.toArray(new int[res.size()][]);
    }

    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if(n==1) return intervals;

        //排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        List<int[]> res=new ArrayList<>();
        for(int[] interval:intervals){
            if(res.isEmpty()||res.get(res.size()-1)[1]<interval[0]){
                res.add(interval);
            }else{
                res.get(res.size()-1)[1]=Math.max(res.get(res.size()-1)[1],interval[1]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
